package com.algorithm.learning.binarysearch;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/17 21:01
 **/
public class 爱吃香蕉的珂珂 {

    public static void main(String[] args) {
        // piles = [30,11,23,4,20], h = 5
        int[] piles = {30,11,23,4,20};
        int h = 6;
        System.out.println(new 爱吃香蕉的珂珂().minEatingSpeed(piles, h));

    }
    public int minEatingSpeed(int[] piles, int h) {
        // 第一步需要找到最大的香蕉树
        int max = 0;
        for (int pile : piles) {
            max = Math.max(max, pile);
        }
        int left = 1;
        int right = max;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int totalTime = computeTotalTime(piles, mid);
            if (totalTime > h) {
                // 如果当前速度mid花费时间大于H，说明吃的太少了，h时间内不能吃完所以香蕉，所以区间为[mid + 1, right]
                left = mid + 1;
            } else {
                // 如果当前速度mid花费时间小于H，说明吃的太多了，不是最小速度，所以区间为[left, mid]
                right = mid;
            }
        }
        return left;
    }

    private int computeTotalTime(int[] piles, int speed) {
        int sum = 0;
        for (int pile : piles) {
            // 算出当前速度下，吃掉每堆香蕉所需要的时间
            // 这里需要向上取整
            sum += (pile + speed - 1) / speed;
        }
        return sum;
    }
}
